public class test5 {
    //力扣 面试题 08.01 三步问题
    public int waysToStep(int n) {
        //1.创建dp数组
        //2.初始化
        //3.状态转移
        //4.返回值

        //处理边界问题
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        //定义一个值进行模处理
        int MOD = (int)1e9+7;

        int[] dp = new int[n+1];
        dp[1] = 1;dp[2] = 2;dp[3] = 4;
        for(int i = 4;i<=n;i++){
            dp[i] = ((dp[i-3] + dp[i-2])%MOD + dp[i-1])%MOD;
        }
        return dp[n];
    }

    //动态规划（滚动数组版）可以优化空间
    public int waysToStep2(int n) {
        //1.创建dp数组
        //2.初始化
        //3.状态转移
        //4.返回值

        //处理边界问题
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        //定义一个值进行模处理
        int MOD = (int)1e9+7;

        int a = 1,b = 2,c = 4;
        int ret = 0;
        for(int i = 4;i<=n;i++){
            ret = ((a + b)%MOD + c)%MOD;
            a = b;
            b = c;
            c = ret;
        }
        return ret;
    }
}
